home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 108_01 / msort.c < prev    next >
Text File  |  1985-11-13  |  8KB  |  256 lines
  1.  
  2. /**********************************************************
  3.  ***                            ***
  4.  ***    Copyright (c) 1981 by David M. Fogg        ***
  5.  ***                            ***
  6.  ***        2632 N.E. Fremont            ***
  7.  ***        Portland, OR 97212            ***
  8.  ***                            ***
  9.  ***        (503) 288-3502{HM} || 223-8033{WK}        ***
  10.  ***                            ***
  11.  ***    Permission is herewith granted for non-     ***
  12.  ***    commercial distribution through the BDS C    ***
  13.  ***    User's Group; any and all forms of commercial   ***
  14.  ***    redistribution are strenuously unwished-for.    ***
  15.  ***                            ***
  16.  **********************************************************/
  17.  
  18. /*
  19.       ---> MSORT.C <--- : sort utility using QuickSort algorithm
  20.  
  21.   (C) Copyright 1980 by David M. Fogg @ New Day Computing - Portland, OR
  22. */
  23.  
  24. /* 29 Oct 80: convert WC->BDS */
  25. /* 30 Oct - add ignore case code */
  26. /* 31 Oct - refine chain code */
  27. /* 5 Nov - fix avg len calc/disp in redlns() */
  28. /* 6 Nov - add chain from CONCORD code */
  29.  
  30. /*
  31.    INFILE is sorted to INFILE.A+, INFILE.B+... for merging
  32.       by MERGE.
  33.    If there is only 1 output file, then INFILE.A+ is renamed
  34.       to INFILE.SRT, and the chain to MERGE is skipped.
  35.    If INFILE has the extension .UNK (i.e., UNsorted Kwic index),
  36.       then the final file name is INFILE.KWC (whether by renaming
  37.       or passing to MERGE), and INFILE.UNK is killed.
  38.  
  39.    ODRIV is where the output file/s go\es. If it is specified,
  40.       it will be passed to MERGE as part of its input file name.
  41.    -I option: Ignore case, i.e., treat uppercase letters as lowercase.
  42.       It's done this way rather then the reverse so that almost all
  43.       of the ASCII special characters (punctuation, etc.) will come
  44.       before the alphabetics in the collating sequence.
  45.       This option, if used, will be passed on to MERGE.
  46.       KWIC turns on this option when chaining to MSORT.
  47.    -R option: sort in reverse (i.e., descending) order.
  48.       This option, if used, will be passed on to merge.
  49.    -L# option: '#' represents a number which is the average line
  50.       length.  If omitted, a value of 30 will be assumed.  If the
  51.       lines to be sorted are significantly longer or shorter, then
  52.       the sort memory buffer can be most efficiently used by informing
  53.       MSORT of the situation.
  54.       KWIC calculates average length for its input file and passes it
  55.       to MSORT.
  56. */
  57.  
  58. #include <dmfio.h>
  59.  
  60. #define MAXLEN    130    /* max length of a line */
  61. #define MARGIN    2000    /* overhead for stack */
  62. #define MINMEM    1024    /* smallest area OK 4 linptr + lbuf */
  63. #define PTRSIZ    2    /* bytes per pointer */
  64. #define AVGLIN    30    /* default average line length */
  65.  
  66. char ibuf[BUFSIZ];    /* ifile buffer */
  67. char obuf[BUFSIZ];    /* ofile buffer */
  68. BOOL eoflag;        /* ifile EOF flag */
  69.  
  70. main(ac, av)
  71. int ac;
  72. char *av[];
  73. {
  74.    char **linptr;        /* ptr to line ptrs */
  75.    char *lbuf;            /* ptr to begin of line buf */
  76.    int nlins;            /* # inp lines read */
  77.    BOOL backwd;         /* backward order sort flag */
  78.    int maxlns;            /* max # of lines allowed */
  79.    int avlen;            /* average line length */
  80.    char *memtop;        /* top of data area */
  81.    unsigned avail;        /* available bytes 4 linptr & lbuf */
  82.    char inam[15];        /* input file name */
  83.    char onam[15];        /* output file name(s) */
  84.    char ext[5];         /* final file name extension */
  85.    int cloc;            /* change ltr loc in onam */
  86.    int xloc;            /* xtension loc in inam */
  87.    int argn;            /* curr comm ln arg # */
  88.    char *arg;            /*  "    "   "   " */
  89.    BOOL igcas;            /* ignore case flag */
  90.  
  91.    _allocp = NULL;
  92.    backwd = NO; avlen = AVGLIN;
  93.    igcas = eoflag = NO;
  94.    strcpy(ext, ".SRT");
  95.  
  96.    if (ac < 2) {
  97.       puts("usage: msort IFILE [ODRIV] [-I -R -L]\n");
  98.       puts("IFILE: file to sort\n");
  99.       puts("ODRIV: (e.g., B:) where to put IFILE.X+ (X=A,B,C...\n");
  100.       puts("   -I: Ignore case (treat uppercase as lowercase)\n");
  101.       puts("   -R: Reverse order sort\n");
  102.       puts("  -L#: average Line Length = # (default 30)\n");
  103.       exit ();
  104.    }
  105.  
  106.    strcpy(inam, av[1]);
  107.    if (fopen(inam, ibuf) == ERROR)
  108.       errxit("Input file error");
  109.  
  110.    for (argn = 2; argn < ac; ++argn) {          /* get/set options */
  111.       arg = av[argn];
  112.       if (*arg == '-')
  113.      switch (arg[1]) {
  114.         case 'I':
  115.            igcas = YES;
  116.            break;
  117.         case 'R': 
  118.            backwd = YES;
  119.            break;
  120.         case 'L':
  121.            if ((avlen = atoi(arg+2)) < 1)
  122.           errxit("Bad average length value");
  123.            break;
  124.         default :
  125.            errxit("Bad option value");
  126.      }
  127.    }
  128.  
  129.    if (ac > 2 && *(av[2]+1) == ':') {      /* set up outfile name */
  130.       strcpy(onam, av[2]);
  131.       if (strlen(onam) > 2) errxit("Bad output drive field");
  132.       strcat(onam, inam + instr(inam, ":"));
  133.    }
  134.    else
  135.       strcpy(onam, inam + instr(inam, ":"));
  136.    if (cloc = instr(onam, "."))
  137.       strcpy(onam + cloc, "A+");
  138.    else
  139.       strcat(onam, ".A+");
  140.  
  141.    cloc = instr(onam, ".A+");
  142.  
  143.    memtop = topofmem() - MARGIN;
  144.    if ((avail = memtop - endext()) < MINMEM)
  145.       errxit("not enough memory");
  146.    maxlns = avail / (avlen + PTRSIZ) - 1;
  147.    if ((linptr = alloc(avail)) == 0)
  148.       errxit("Memory allocation error");
  149.    lbuf = linptr + maxlns;        /* lbuf starts abuv its ptrs */
  150.    printf("Memory available: %u   Max lines: %d\n", avail, maxlns);
  151.  
  152.    /*
  153.       >>------> MAIN LOOP <------<<
  154.    */
  155.    while ((nlins = redlns(linptr, lbuf, maxlns, memtop)) > 0) {
  156.       printf(" %d lines read\n", nlins);
  157.       quick(linptr, 0, nlins - 1, backwd, igcas);
  158.       ritlns(linptr, nlins, onam);
  159.       onam[cloc] = ++onam[cloc];
  160.    }
  161.  
  162. /*
  163.       >>>---------> EGRESS
  164. */
  165.    fclose(ibuf);
  166.  
  167.    if (xloc = instr(inam, ".UNK")) {
  168.       unlink(inam);
  169.       strcpy(ext, ".KWC");
  170.    }
  171.    else if (xloc = instr(inam, ".UNC")) {
  172.       unlink(inam);
  173.       strcpy(ext, ".CON");
  174.    }
  175.    else
  176.       xloc = instr(inam, ".");
  177.  
  178.    if (xloc)
  179.       strcpy(inam+xloc, ext+1);
  180.    else
  181.       strcat(inam, ext);
  182.  
  183.    if (onam[cloc] == 'B') {        /* only 1 file: rename */
  184.       onam[cloc] = 'A';
  185.       unlink(inam);       /* avoid multiple files w/ same name!!! */
  186.       if (rename(onam, inam) == ERROR)
  187.      errxit("File rename error");
  188.    }
  189.    else {                /* >1 file: --> merge */
  190.       onam[--cloc] = NULL;
  191.       if (igcas) {
  192.      printf("\n--> merge %s %s -I\n", onam, inam);
  193.      execl("merge", onam, inam, "-I", 0);
  194.       }
  195.       else {
  196.      printf("\n--> merge %s %s\n", onam, inam);
  197.      execl("merge", onam, inam, 0);
  198.       }
  199.    }
  200. }
  201.  
  202. /************************************************************/
  203.  
  204. redlns (linptr, lbuf, maxlns, mtop)     /* <--- INPUT LINES <--- */
  205. char **linptr;
  206. char *lbuf;
  207. int maxlns;
  208. char *mtop;
  209.  
  210. /***   Reads input lines from ifile into heap area
  211.   **   Pointer to each line goes into linptr
  212.   **   RETURNS: number of lines read
  213. */
  214. {
  215.    int len;
  216.    unsigned avl, nlines;
  217.    char *pbuf;            /* pointo curr pos in lbuf */
  218.    int rv;            /* ret val from fgets */
  219.  
  220.    nlines = 0;
  221.    pbuf = lbuf;
  222.  
  223.    if (eoflag) return (0);
  224.  
  225.    while (nlines < maxlns && pbuf+MAXLEN < mtop) {
  226.       rv = fgets(pbuf, ibuf);
  227.       if (rv == 0) {
  228.      eoflag = YES;
  229.      break;
  230.       }
  231.       len = strlen(pbuf);
  232.       linptr[nlines++] = pbuf;
  233.       pbuf += len;
  234.       *(pbuf-1) = '\0';      /* zap newline */
  235.    }
  236.    if (nlines) {
  237.       avl = pbuf - lbuf; avl = avl / nlines;
  238.       printf("Average line length = %u\n", avl);
  239.    }
  240.    return (nlines);
  241. }
  242.  
  243.  
  244. ritlns (linptr, nlins, onam)    /* ---> WRITE OUTPUT LINES ---> */
  245. char **linptr;
  246. int nlins;
  247. char *onam;
  248. {
  249.    if (fcreat(onam, obuf) == ERROR)
  250.       errxit("error creating o/p file");
  251.  
  252.    while (nlins-- > 0)
  253.       fprintf(obuf, "%s\n", *linptr++);
  254.    oclose(obuf);
  255. }
  256.